显然,题目求的是:
有一个与莫比乌斯函数有关的性质:
将 往前移,然后是一个非常经典的式子了
令,将它放到前面枚举:
前面的可以用数轮分块解决,后面的可以将每个数对它的倍数的贡献计算,最后做一遍前缀和也可以分块了。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 10000000;
int t , a , b , d;
int k , prime[ MAXN + 5 ] , mu[ MAXN + 5 ];
long long f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ k ] = i;
mu[ i ] = -1;
}
for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
}
void Init( ) {
sieve( );
for( int j = 1 ; j <= k ; j ++ )
for( int i = 1 ; 1ll * i * prime[ j ] <= MAXN ; i ++ )
f[ i * prime[ j ] ] += mu[ i ];
for( int i = 2 ; i <= MAXN ; i ++ )
f[ i ] += f[ i - 1 ];
}
long long solve( int n , int m ) {
long long Ans = 0;
for( int l = 1 , r ; l <= min( n , m ) ; l = r + 1 ) {
r = min( n / ( n / l ) , m / ( m / l ) );
Ans += 1ll * ( n / l ) * ( m / l ) * ( f[ r ] - f[ l - 1 ] );
}
return Ans;
}
int main( ) {
Init( );
scanf("%d",&t);
while( t -- ) {
scanf("%d %d",&a,&b);
printf("%lld\n",solve( a , b ));
}
return 0;
}